package leetcode

import (
	"sort"
	"strconv"
	"strings"
)

//寻找最大连续无重复子字符串，移动括号法，双index法：移动后面的index先，如果遇见重复的就移前面的，知道没重复了，
//注意右边索引要-1以给最后一个留个查看的位置
func LengthOfLongestSubstring(s string) int {
	var maxLength int //结果
	var rk = -1       //右index
	//用于标记重复
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		//先把移动完了的括号外的删除了
		if i != 0 {
			delete(m, s[i-1])
		}
		for rk+1 < len(s) {
			if _, ok := m[s[rk+1]]; ok { //如果有重复的就停止右侧index移动
				break
			} else { //否则继续移动，并且将rk+1的map统计在内
				rk++
				m[s[rk]]++
			}
		}
		//记录最长的长度
		if rk-i+1 > maxLength {
			maxLength = rk - i + 1
		}
	}
	return maxLength
}

//动态规划求最长回文子串
func LongestPalindrome(s string) string {
	begin := 0
	end := 0
	//特殊情况
	if len(s) < 2 {
		return s
	}
	//用于存储已知的回文
	arr := make([][]bool, len(s))
	for i := 0; i < len(s); i++ {
		arr[i] = make([]bool, len(s))
		//单字符都是回文
		arr[i][i] = true
	}
	//需要注意遍历的顺序，j靠右需要依赖比自己小的存储矩阵，i需要依赖比自己大的存储矩阵
	//因此j需要从
	//j代表靠右的index
	for j := 1; j < len(s); j++ {
		//i代表靠左的index
		for i := j - 1; i >= 0; i-- {
			if s[i] != s[j] {
				arr[i][j] = false
			} else {
				//如果j和i相邻或者相隔一个数都是回文
				if j-i < 3 {
					arr[i][j] = true
				} else {
					//需要注意遍历的顺序，j靠右需要依赖比自己小的存储矩阵，i需要依赖比自己大的存储矩阵
					//否则就取决于它的子串是不是回文
					arr[i][j] = arr[i+1][j-1]

				}
			}
			//找最长的回文子串
			if arr[i][j] && j-i > end-begin {
				begin = i
				end = j
			}
		}
	}

	return s[begin : end+1]
}

//回溯法求所有手机字母组合
var (
	phoneMap = map[string]string{
		"2": "abc",
		"3": "def",
		"4": "ghi",
		"5": "jkl",
		"6": "mno",
		"7": "pqrs",
		"8": "tuv",
		"9": "wxyz",
	}
	res []string
)

func LetterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	var builder = ""
	res = []string{}
	backtrack(digits, builder, 0)

	return res
}

func backtrack(digits, builder string, index int) {
	if index == len(digits) {
		res = append(res, builder)
	} else {
		letter := phoneMap[string(digits[index])]
		index++
		//一个数字对于了好几种可能都需要考虑
		for i := 0; i < len(letter); i++ {
			//回溯，下层结果回来需要换一个本层的可能
			//23
			//⬆
			//a		b		c
			//
			//23
			// ⬆
			//def	def		def
			builder += string(letter[i])
			backtrack(digits, builder, index)
			builder = builder[0 : len(builder)-1]
		}
	}
}

//求几个字符串的最长公共前缀
func LongestCommonPrefix(strs []string) string {
	var res string
	//特殊情况
	if len(strs) == 0 {
		return res
	}
	if len(strs) == 1 {
		return strs[0]
	}
	//暴力法解，公共前缀只用遍历第一个字符串就行
OuterLoop:
	for i := 0; i < len(strs[0]); i++ {
		//遍历之后的字符串
		for j := 1; j < len(strs); j++ {
			//如果发现前缀不匹配了，那就直接终端
			if len(strs[j])-1 < i || strs[0][0:i+1] != strs[j][0:i+1] {
				break OuterLoop
			}
		}
		res += string(strs[0][i])
	}

	return res
}

//赎金信，字符串匹配
func canConstruct(ransomNote string, magazine string) bool {
	m := make(map[uint8]int)
	for i := 0; i < len(magazine); i++ {
		if _, ok := m[magazine[i]]; !ok {
			m[magazine[i]] = 1
		} else {
			m[magazine[i]]++
		}
	}
	for i := 0; i < len(ransomNote); i++ {
		if k, ok := m[ransomNote[i]]; !ok || k == 0 {
			return false
		} else {
			m[ransomNote[i]]--
		}
	}
	return true
}

//截断句子
func truncateSentence(s string, k int) string {
	ss := strings.Split(s, " ")
	if len(ss) < k {
		return s
	}
	var res string
	for i := 0; i < k; i++ {
		if i != k-1 {
			res += ss[i] + " "
		} else {
			res += ss[i]
		}
	}
	return res
}

//1446. 连续字符，返回最长连续字符子串
func maxPower(s string) int {
	i, max := 0, 0
	for i < len(s) {
		max_i := 1
		j := i + 1
		for ; j < len(s); j++ {
			if s[i] == s[j] {
				max_i++
			} else {
				break
			}
		}
		i = j
		if max_i > max {
			max = max_i
		}
	}
	return max
}

var (
	ordinary = [13]int{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365}
	leap     = [13]int{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
	week     = [7]string{"Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday"}
)

//1154. 一年中的第几天
func dayOfYear(date string) int {
	bs := strings.Split(date, "-")
	year, _ := strconv.ParseInt(bs[0], 10, 16)
	month, _ := strconv.ParseInt(bs[1], 10, 8)
	day, _ := strconv.ParseInt(bs[2], 10, 8)
	res := 0
	if (year%4 == 0 && year%100 != 0) || year%400 == 0 {
		res += leap[month-1] + int(day)
	} else {
		res += ordinary[month-1] + int(day)
	}
	return res
}

//1185. 一周中的第几天
func dayOfTheWeek(day int, month int, year int) string {
	days := 365*(year-1971) + (year-1969)/4
	if (year%4 == 0 && year%100 != 0) || year%400 == 0 {
		days += leap[month-1]
	} else {
		days += ordinary[month-1]
	}
	days += day
	return week[days%7]
}

//686. 重复叠加字符串匹配
func repeatedStringMatch(a string, b string) int {
	if b == "" {
		return 0
	}
	c := a
	sum := 1
	//关键点在此，因为一个符合的终结条件，需要包含一段前后拼接成的
	//a的字符串，所以需要2*len(a),还应该最后得到的比len(b)长
	for len(c) < 2*len(a)+len(b) {
		if strings.Contains(c, b) {
			return sum
		}
		c += a
		sum++
	}
	if strings.Contains(c, b) {
		return sum
	}
	return -1
}

//1576. 替换所有的问号
func modifyString(s string) string {
	bs := make([]byte, len(s))
	for i := 0; i < len(s); i++ {
		if s[i] == '?' {
			if i == 0 {
				bs[i] = 'a'
			} else {
				bs[i] = 'a' + (bs[i-1]+1)%26
			}
		} else {
			bs[i] = s[i]
			if i > 0 && bs[i-1] == bs[i] {
				bs[i-1] = 'a' + (bs[i-1]+1)%26
			}
		}
	}
	return string(bs)
}

//1078. Bigram 分词
func findOcurrences(text string, first string, second string) []string {
	var res = []string{}
	texts := strings.Split(text, " ")
	for i := 0; i < len(texts)-2; i++ {
		if texts[i] == first && texts[i+1] == second {
			res = append(res, texts[i+2])
		}
	}
	return res
}

//472. 连接词
func findAllConcatenatedWordsInADict(words []string) []string {
	//排序
	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })

	var t = &TrieTree{
		root: &TrieNode{
			children:     [26]*TrieNode{},
			isEndingChar: false,
		},
	}
	res := make([]string, 0)

	for i := range words {
		s := words[i]
		if s == "" {
			continue
		}
		if t.dfs(s) {
			//如果是连接词，那么无需添加到字典树里，因为里面全是树里包含的
			res = append(res, s)
		} else {
			t.Insert(s)
		}
	}
	return res
}

//巧用一个深度查找
func (t *TrieTree) dfs(word string) bool {
	//递归结束条件
	if word == "" {
		return true
	}
	node := t.root
	for i, ch := range word {
		node = node.children[ch-'a']
		//不匹配
		if node == nil {
			return false
		}
		//匹配则验证子串
		if node.isEndingChar && t.dfs(word[i+1:]) {
			return true
		}
	}
	return false
}

type TrieTree struct {
	root *TrieNode
}

type TrieNode struct {
	children     [26]*TrieNode
	isEndingChar bool
}

func (t *TrieTree) Insert(s string) {
	if t.root == nil {
		t.root = &TrieNode{
			children:     [26]*TrieNode{},
			isEndingChar: false,
		}
	}
	p := t.root
	for i := 0; i < len(s); i++ {
		index := s[i] - 'a'
		if p.children[index] == nil {
			p.children[index] = &TrieNode{
				children:     [26]*TrieNode{},
				isEndingChar: false,
			}
		}
		p = p.children[index]
	}
	p.isEndingChar = true
}

//58. 最后一个单词的长度
func lengthOfLastWord(s string) int {
	res := 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == ' ' && res == 0 {
			continue
		}
		if s[i] != ' ' {
			res++
		} else {
			break
		}
	}
	return res
}

//1763. 最长的美好子字符串
func longestNiceSubstring(s string) string {
	res := ""
	check := func(substr string) bool {
		bs := []byte(substr)
		sort.Slice(bs, func(i, j int) bool { return bs[i] < bs[j] })
		bsnew := make([]byte, 0)
		bsnew = append(bsnew, bs[0])
		for i := 1; i < len(bs); i++ {
			if bs[i] != bsnew[len(bsnew)-1] {
				bsnew = append(bsnew, bs[i])
			}
		}
		if len(bsnew)%2 != 0 {
			return false
		}
		i, j := 0, len(bsnew)/2
		for j < len(bsnew) {
			if bsnew[i] != bsnew[j]-32 {
				return false
			}
			i++
			j++
		}
		return true
	}
	for i := 0; i < len(s); i++ {
		for j := len(s) - 1; j > i; j-- {
			if check(s[i:j+1]) && j-i+1 > len(res) {
				res = s[i : j+1]
			}
		}
	}
	return res
}

//2000. 反转单词前缀
func reversePrefix(word string, ch byte) string {
	i := 0
	for ; i < len(word); i++ {
		if word[i] == ch {
			break
		}
	}
	if i == len(word) {
		return word
	}
	back := word[i+1 : len(word)]
	front := ""
	for ; i >= 0; i-- {
		front += string(word[i])
	}
	return front + back
}

//344. 反转字符串
func reverseString(s []byte) {
	low, high := 0, len(s)-1
	for low <= high {
		s[low], s[high] = s[high], s[low]
		low++
		high--
	}
}

//151. 翻转字符串里的单词
func reverseWords(s string) string {
	res := ""
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] != ' ' {
			j := i
			for ; j >= 0; j-- {
				if s[j] == ' ' {
					break
				}
			}
			res = res + " " + s[j+1:i+1]
			i = j
		}
	}
	if len(res) > 0 {
		return res[1:]
	}
	return res
}

//49. 字母异位词分组
func groupAnagrams(strs []string) [][]string {
	m := make(map[string][]string)
	res := make([][]string, 0)
	var temp []byte
	for i := range strs {
		temp = []byte(strs[i])
		sort.Slice(temp, func(i, j int) bool {
			return temp[i] < temp[j]
		})
		m[string(temp)] = append(m[string(temp)], strs[i])
	}
	for _, v := range m {
		res = append(res, v)
	}
	return res
}

//43. 字符串相乘
func multiply(num1 string, num2 string) string {
	bs1, bs2 := []byte(strRevers(num1)), []byte(strRevers(num2))
	for i := range bs1 {
		bs1[i] -= '0'
	}
	for i := range bs2 {
		bs2[i] -= '0'
	}
	ans := make([]int, len(bs1)+len(bs2))
	//最后再进位
	for i := 0; i < len(bs1); i++ {
		for j := 0; j < len(bs2); j++ {
			ans[j+i] += int(bs1[i]) * int(bs2[j])
		}
	}
	for i := 0; i < len(ans)-1; i++ {
		ans[i+1] += ans[i] / 10
		ans[i] = ans[i] % 10
	}
	index:=len(ans)-1
	for ;index>0;index--{
		if ans[index]!=0{
			break
		}

	}
	ans=ans[:index+1]
	var res=""
	for i:=range ans{
		res=string(byte(ans[i])+'0')+res
	}
	return res
}

func strRevers(s string) string {
	bs := []byte(s)
	for i := 0; i < len(s)/2; i++ {
		bs[i], bs[len(s)-1-i] = bs[len(s)-1-i], bs[i]
	}
	return string(bs)
}
//76. 最小覆盖子串
func minWindow(s string, t string) string {
	m:=make(map[byte]int)
	for i:=range t{
		m[t[i]]++
	}
	check:= func()bool {
		for _,v:=range m{
			if v>0{
				return false
			}
		}
		return true
	}
	left,right:=0,0
	res:=""
	if _,ok:=m[s[left]];ok{
		m[s[left]]--
	}
	for left<=right&&right<len(s)&&left<len(s){
		if check(){
			if len(res)==0||len(res)>right-left+1{
				res=s[left:right+1]
			}
			if _,ok:=m[s[left]];ok{
				m[s[left]]++
			}
			left++
		}else {
			right++
			if right<len(s){
				if _,ok:=m[s[right]];ok{
					m[s[right]]--
				}
			}
		}
	}
	return res
}
//438. 找到字符串中所有字母异位词
func findAnagrams(s string, p string) []int {
	res:=[]int{}
	if len(s)<len(p){
		return res
	}
	ss,ps:=[26]int{},[26]int{}
	for i:=0;i<len(p);i++{
		ss[s[i]-'a']++
		ps[p[i]-'a']++
	}
	ss[s[len(p)-1]-'a']--
	for i:=0;i<=len(s)-len(p);i++{
		ss[s[i+len(p)-1]-'a']++
		if ss==ps{
			res=append(res, i)
		}
		ss[s[i]-'a']--
	}
	return res
}